public class test07 {
    /*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
        public Node connect(Node root) {
            if(root==null){
                return root;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int len = queue.size();
                Node pre = queue.poll();
                if(pre.left!=null){
                    queue.offer(pre.left);
                }
                if(pre.right!=null){
                    queue.offer(pre.right);
                }

                for(int i = 1;i<len;i++){
                    Node cur = queue.poll();
                    if(cur.left!=null){
                        queue.offer(cur.left);
                    }
                    if(cur.right!=null){
                        queue.offer(cur.right);
                    }
                    pre.next = cur;
                    pre = cur;
                }
            }
            return root;
        }
}
